1. Technical Field:
The present invention is related to a method and system to be utilized in data communications. In particular, the present invention is related to a method and system to be utilized in data communications involving at least one data communications network. Yet still more particularly, the present invention is related to a method and system, to be utilized in data communications involving at least one data communications network having at least one multiprocessor network node.
2. Description of the Related Art:
Data communications is the transfer of data from one or more data sources to one or more data sinks that is accomplished (a) via one or more data links between the one or more sources and one or more sinks, and (b) according to a protocol. Weik, Communications Standard Dictionary 203 (3 ed. 1996). A data link is the means of connecting facilities or equipment at one location to facilities or equipment at another location for the purpose of receiving the data. Weik, Communications Standard Dictionary 206 (3 ed. 1996). A protocol, in communications, computer, data processing, and control systems, is a set of formal conventions that govern the format and control the interactions between two communicating functional elements in order to achieve efficient and understandable communications. Weik, Communications Standard Dictionary 770 (3 ed. 1996).
A data communications network is the interconnection of three or more communicating entities (e.g., data sources and/or sinks) over one or more data links. Weik, Communications Standard Dictionary 618 (3 ed. 1996). The branch of science and technology that is devoted to the study and analyses of the configurations and properties of networks makes use of what are known as network topologies. Weik, Communications Standard Dictionary 622 (3 ed. 1996). A network topology is typically a graphical representation of the specific logical arrangement, from a communications standpoint, of elements in a network, irrespective of such network elements' actual physical connection. In the art and science of network topology, different networks are distinguished by their different network topologies.
In network topology, each communicating entity in a network is depicted as a graphical point, or node. These nodes are abstract representations of locations in an actual physical network at which one or more data transmission lines are interconnected. Weik, Communications Standard Dictionary 622 (3 ed. 1996).
There are multitudinous known network topologies (e.g. mesh, star, fully connected, etc., and hybrids of such known network topologies). One such well-known network topology is the star network topology, which can be utilized to illustrate a problem that exists generally in the field of data communications involving networks having nodes.
A star network topology is a radial (starlike) configuration of communications network nodes such that (a) each endpoint node is connected via a single branch directly to the central node that serves as a central distribution node, and (b) each endpoint node can communicate with any other node only via the central node and two branches. The central node serves as a distribution node to all the endpoint nodes, including the originating node, or to selected endpoint nodes, depending upon whether the central node is an active or passive node. Weik, Communications Standard Dictionary 625 (3 ed. 1996).
FIG. 1 illustrates a star network topology. Shown is central node 100. Connected to central node 100 are endpoint nodes 102-116. These endpoints, or end stations, are connected to central node 100 via data links 122-136, respectively. The topology of the network makes clear that all communications between endpoints must transit central node 100.
In operation, central node 100 receives packetized data (in its most generic sense packetized data typically consists of a message field, a source field indicating the source node of the packetized data, and a destination field indicating the destination node (or data sink) of the packetized data) from endpoint nodes 102-116 over their respective data links. Upon reception of such packetized data, central node 100 reads the destination field, determines which data link the packetized data must be sent over to reach the destination indicated in the destination field, and then subsequently sends the packetized data over the appropriate data link. Central node 100 must do the foregoing (receive the packetized data, read the destination field, and then transmit the packetized data over the appropriate link) for each unit of packetized data received.
It is common for several end stations to desire to communicate with other end stations virtually simultaneously. In such situations, central node 100 is called upon to read the destination fields of several different units of packetized data, and forward the packetized data unit to the appropriate destination endpoint node, all at essentially the same time.
In old-style nodes performing the function of central node 100, this function was achieved by buffering (placing in temporary storage) one or more of the packetized data units, and then processing the stored data units one at a time. Another way to state this is that the packetized data units arriving virtually simultaneously were enqueued (made to wait in line) and would only be processed (i.e., destination field read and the packets forwarded to the appropriate destination) after the packetized data units ahead of them in the queue had been processed.
This need for enqueuing arose from the fact that in old-style nodes there was only one processor (or "thinker"), and that processor could only process one packetized data unit at a time. Thus, if more than one packetized data unit appeared at central node 100 virtually simultaneously, many of such packetized data units would have to "wait their turn" until the processor was able to process them.
As network data traffic increased, it was found that such enqueuing began to result in unreasonable communication delays (i.e., the wait in line, or in the "queue," became too long for the communications needs of particular endpoint nodes to be satisfied). This excessive delay problem was alleviated by placing multiple processors in central node 100.
Placing multiple processors (or "thinkers") in central node 100, essentially gave central node 100 the ability to simultaneously process as many packetized data units as there were processors. For example, if endpoint nodes 102, 104, and 106 transmitted packetized data destined for endpoint nodes 108, 110, and 112, respectively, to central node 100 virtually simultaneously, in the old-style nodes the packetized data arriving first at central node 100 would have been read and forwarded, while the two later arrivals would have been enqueued and made to wait their turn until the single central node 100 processor was ready for them.
In the new-style nodes, if central node 100 has at least three processors, and those processors are not engaged in processing other data, the three packetized data units will be handed over to the individual processors for processing almost immediately upon reception. That is, the multiple processors in central node 100 have alleviated the wait associated with the enqueuing. Subsequent to the multiple processors within central node 100 determining where the packetized data is to go (i.e., reading the destination information), the packetized data is transmitted over the appropriate data link associated with the destination station.
While the new-style nodes incorporating multiple processors have greatly improved communications efficiency, they have also inadvertently given rise to an attendant problem. That problem is the inability to ensure that the sequence of packetized data units entering the central node on one specific data link will be preserved upon those same packetized data units exiting the central node on another specific data link (notice that old-style nodes preserved such sequence merely as a byproduct of the enqueuing). This problem can be illustrated with reference again to FIG. 1.
This problem can be illustrated with reference again to FIG. 1. Assume the endpoint node 104 transmits four packetized data units in sequence to be delivered to endpoint node 116. Assume also that central node 100 has at least four processors. Further assume that no other stations are transmitting while endpoint 104 is transmitting.
Upon receipt of the four packetized data units through the port (entry and exit points of nodes associated with specific data links are generally referred to as "ports") of central node 100 associated with data link 124, central node 100 essentially contemporaneously delivers them to individual processors in the sequence the packetized data units were received. Now, assuming that the clock speed (a factor which influences the speed in which data can be processed by a processor) of the processor in which the third packetized data unit received is faster than those of the other three processors. As a consequence of this, assume that the processor holding the third received packetized data unit completes its processing first. Consequently, the third in received packetized data unit will be the first to be transmitted through the port of central node 100 associated with data link 136, and thus the third in sequence data packet transmitted by endpoint node 104 is the first received by destination endpoint node 116. Thus, the sequence of the packetized data units has been destroyed.
Such destruction of sequencing is a byproduct of multiple processor nodes. There are many applications, well known in the art, where such loss of sequence is unacceptable (e.g., real-time video conferencing, or real-time remote patient monitoring). However, as was noted above, since multiple processor nodes have very real benefits it is desirable to continue using them, albeit in a way that does not destroy sequencing of packetized data units.
It is apparent from the foregoing that a need exists for a method and system, which can be used with multiprocessor network nodes, and which will ensure that the sequence in which data units enter one or more specific ports of a multiple processor node is preserved when those same data units subsequently exit from the multiprocessor node. It would be further advantageous is the method and system could be implemented in new network nodes as well as retrofitted to existing network nodes.